<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>算法导论-第十二章 二叉查找树 | 章军的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="算法导论十二章 二叉查找树">
<meta name="keywords" content="data struct">
<meta property="og:type" content="article">
<meta property="og:title" content="算法导论-第十二章 二叉查找树">
<meta property="og:url" content="http://octopuscloud.top/2019/09/11/十二章-二叉搜索树/index.html">
<meta property="og:site_name" content="章军的博客">
<meta property="og:description" content="算法导论十二章 二叉查找树">
<meta property="og:locale" content="China">
<meta property="og:updated_time" content="2019-09-11T04:27:11.760Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法导论-第十二章 二叉查找树">
<meta name="twitter:description" content="算法导论十二章 二叉查找树">
  
    <link rel="alternate" href="/atom.xml" title="章军的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">章军的博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://octopuscloud.top"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-十二章-二叉搜索树" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/09/11/十二章-二叉搜索树/" class="article-date">
  <time datetime="2019-09-11T04:27:11.760Z" itemprop="datePublished">2019-09-11</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/ReadNote/">ReadNote</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      算法导论-第十二章 二叉查找树
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="算法导论十二章-二叉查找树"><a href="#算法导论十二章-二叉查找树" class="headerlink" title="算法导论十二章 二叉查找树"></a>算法导论十二章 二叉查找树</h1><a id="more"></a>
<h2 id="二叉查找树的基本性质"><a href="#二叉查找树的基本性质" class="headerlink" title="二叉查找树的基本性质"></a>二叉查找树的基本性质</h2><ul>
<li>查找树是一种数据结构，支持多种多台集合操作，包括 SEARCH, DELETE, MININUM, MAXINUM, PREDECESSOR, SUCCESSOR, INSERT 等，且时间为 Ѳ(lg n) — 完全二叉树。</li>
<li>根节点的 key 值是大于左子节点的 key 值，小于右子节点的 key 值。</li>
<li>数据结构一个由 key, satellite date, left children pointer, right children pointer 组成 .</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">struct Node &#123;</span><br><span class="line">  key filed;</span><br><span class="line">  satellite data filed;</span><br><span class="line">  left child pointer;</span><br><span class="line">  right child pointer;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li><p>遍历二叉树的三种方法.</p>
<p>前序遍历：根节点关键字在其左右子节点之前；<br>中序遍历：根节点关键字在左右子节点之间；<br>后序遍历：根节点关键之在左右子节点之后。</p>
</li>
</ul>
<h2 id="二叉树的操作"><a href="#二叉树的操作" class="headerlink" title="二叉树的操作"></a>二叉树的操作</h2><h3 id="给定关键字查询"><a href="#给定关键字查询" class="headerlink" title="给定关键字查询"></a>给定关键字查询</h3>  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">@@@@ for recursion </span><br><span class="line">TREE-SEARCH(x, k)</span><br><span class="line">if x == NIL or k == key[x]</span><br><span class="line">  then return x</span><br><span class="line">if k &lt; key[x]</span><br><span class="line">  return TREE-SEARCH(left[x], k)</span><br><span class="line">else</span><br><span class="line">  return TREE-SEARCH(right[x], k)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">@@@ no recursion</span><br><span class="line">TREE-SEARCH(x, k)</span><br><span class="line">while x != NIL and k != key[x]</span><br><span class="line">  if k &lt; key[x] </span><br><span class="line">    x = left[x]</span><br><span class="line">  else</span><br><span class="line">    x = right[x]</span><br><span class="line">return x</span><br></pre></td></tr></table></figure>
<h3 id="最大值和最小值"><a href="#最大值和最小值" class="headerlink" title="最大值和最小值"></a>最大值和最小值</h3>  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">@@@ MIN</span><br><span class="line">MININUM(x)</span><br><span class="line">while x != NIL</span><br><span class="line">  x = left(x)</span><br><span class="line">return x</span><br><span class="line"></span><br><span class="line">@@@ MAX</span><br><span class="line">MAXINUM(x)</span><br><span class="line">while x != NULL</span><br><span class="line">  x = right[x]</span><br><span class="line">return x</span><br></pre></td></tr></table></figure>
<h3 id="前趋和后继"><a href="#前趋和后继" class="headerlink" title="前趋和后继"></a>前趋和后继</h3><pre><code>在树中寻找后继节点时，先会判断当前节点的右节点是否存在. 如果右节点存在，去找一右节点为根节点的树中最小值。
</code></pre><p>  则此值为当前节点的后继。如果当前节点没有右子节点，则应当回溯父亲节点，找到某个节点是其父亲节点的左节点结束。<br>  找到的节点叫做最低先祖节点，同时也是要寻找的后继节点。</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">@@@ SUCCESSOR</span><br><span class="line">SUCCESSOR(x)</span><br><span class="line">  if right[x] != NILL</span><br><span class="line">    return MININUM(right[x])</span><br><span class="line">  y = father[x]</span><br><span class="line">  while y != NUL and x == right[y]</span><br><span class="line">    x = y</span><br><span class="line">    y = father[y]</span><br><span class="line">  return y</span><br><span class="line"></span><br><span class="line">@@@ PREDECESSOR</span><br><span class="line">PREDECESSOR(x)</span><br><span class="line">  if left[x] != NIL</span><br><span class="line">    return MAXINUM(left[x])</span><br><span class="line"></span><br><span class="line">  y = father[x]</span><br><span class="line">  while y != NIL and x = left[x]</span><br><span class="line">    x = y</span><br><span class="line">    y = father[y]</span><br><span class="line"></span><br><span class="line">  return y</span><br></pre></td></tr></table></figure>
<h3 id="插入和删除"><a href="#插入和删除" class="headerlink" title="插入和删除"></a>插入和删除</h3><pre><code>在执行插入操作时，会根据将要插入的节点的 key 值来确认他的父亲节点，在用插入点的 key 值和父亲节点的 key 值比较，大于父亲节点 key 值，
</code></pre><p>  插入父亲节点右子节点，小于父亲节点子节点，插入父亲节点左子节点。<br>    在执行删除操作时，会先判断需要删除节点的子节点个数。如果删除节点没有子节点，则将删除节点直接删除即可。如果删除节点右一个子节点，则<br>  将删除节点的父亲节点指向删除节点的子节点，这样就将节点从树中删除了。如果删除节点右两个子节点，则会删除这节点的后继节点，然后用后继节<br>  点的数据覆盖删除节点。</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line">@@@ INSERT</span><br><span class="line">INSERT(T, z)</span><br><span class="line">  find the insert node </span><br><span class="line">  y = NIL</span><br><span class="line">  x = root[T]</span><br><span class="line">  while x != NIL and </span><br><span class="line">    y = x</span><br><span class="line">    if key[z] &lt; key[x]</span><br><span class="line">      x = left[x]</span><br><span class="line">    else</span><br><span class="line">      x = right[x]</span><br><span class="line"></span><br><span class="line">  father[z] = y</span><br><span class="line">  if y == NIL</span><br><span class="line">    root[T] = z</span><br><span class="line">  else if key[z] &lt; key[x]</span><br><span class="line">    left[x] = z</span><br><span class="line">  else </span><br><span class="line">    right[x] = z</span><br><span class="line"></span><br><span class="line">@@@ DELETE</span><br><span class="line">DELETE(T, z)</span><br><span class="line"></span><br><span class="line">  find the delete node </span><br><span class="line">  if left[z] == NIL and right[z] == NIL</span><br><span class="line">    y = z</span><br><span class="line">  else</span><br><span class="line">    y = SUCCESSOR(T, Z)</span><br><span class="line">  </span><br><span class="line">  there are two sub or one sub for delete node</span><br><span class="line"></span><br><span class="line">  if left[y] != NIL</span><br><span class="line">    x = left[y]</span><br><span class="line">  else</span><br><span class="line">    x = right[y]</span><br><span class="line">  </span><br><span class="line">  delete the node y</span><br><span class="line">  if father[y] == NIL</span><br><span class="line">    root[T] = z</span><br><span class="line">  else if y = left[ father[y] ]</span><br><span class="line">    left[ father[y] ] = x</span><br><span class="line">  else </span><br><span class="line">    right[ father[y] ] = x</span><br><span class="line"></span><br><span class="line">  if y != z</span><br><span class="line">    key[z] = key[y]</span><br><span class="line">    copy other data filed .</span><br><span class="line">return y</span><br></pre></td></tr></table></figure>
<h2 id="code-1"><a href="#code-1" class="headerlink" title="[code][1]"></a>[code][1]</h2><p>1:  <a href="mailto:git@github.com" target="_blank" rel="noopener">git@github.com</a>:singledo/SortCode.git</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://octopuscloud.top/2019/09/11/十二章-二叉搜索树/" data-id="ck2773eqf001k69fzw1618ots" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/data-struct/">data struct</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/09/29/IPv6-NDP/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          IPv6 NDP
        
      </div>
    </a>
  
  
    <a href="/2019/09/11/SegmentationFault-Debug/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title"></div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/RFC/">RFC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/RFC-protocol/">RFC protocol</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ReadNote/">ReadNote</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/protocols/">protocols</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/tools/">tools</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Struct/">Data Struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ethernet-II/">Ethernet II</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Frame-Format/">Frame Format</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/I2C/">I2C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/IPv6/">IPv6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Neighbour-Discover-Protocol/">Neighbour Discover Protocol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RFC/">RFC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SNMP/">SNMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/arthmetic/">arthmetic</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cgdb/">cgdb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/chapter-15/">chapter 15</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-struct/">data struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/deb/">deb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/defalt-path-for-so-file/">defalt path for so file</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/editer/">editer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/file-system/">file system</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/gdb-debug/">gdb debug</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pointer-array/">pointer, array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pseudocode/">pseudocode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rb-tree/">rb tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sort/">sort</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ssh-key/">ssh key</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/symbol/">symbol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tools/">tools</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/图/">图</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/通信协议/">通信协议</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/C/" style="font-size: 10px;">C</a> <a href="/tags/Data-Struct/" style="font-size: 10px;">Data Struct</a> <a href="/tags/Ethernet-II/" style="font-size: 10px;">Ethernet II</a> <a href="/tags/Frame-Format/" style="font-size: 10px;">Frame Format</a> <a href="/tags/I2C/" style="font-size: 10px;">I2C</a> <a href="/tags/IPv6/" style="font-size: 15px;">IPv6</a> <a href="/tags/Neighbour-Discover-Protocol/" style="font-size: 10px;">Neighbour Discover Protocol</a> <a href="/tags/RFC/" style="font-size: 10px;">RFC</a> <a href="/tags/SNMP/" style="font-size: 10px;">SNMP</a> <a href="/tags/arthmetic/" style="font-size: 10px;">arthmetic</a> <a href="/tags/cgdb/" style="font-size: 10px;">cgdb</a> <a href="/tags/chapter-15/" style="font-size: 10px;">chapter 15</a> <a href="/tags/data-struct/" style="font-size: 15px;">data struct</a> <a href="/tags/deb/" style="font-size: 10px;">deb</a> <a href="/tags/defalt-path-for-so-file/" style="font-size: 10px;">defalt path for so file</a> <a href="/tags/editer/" style="font-size: 10px;">editer</a> <a href="/tags/file-system/" style="font-size: 10px;">file system</a> <a href="/tags/gdb-debug/" style="font-size: 10px;">gdb debug</a> <a href="/tags/hash/" style="font-size: 10px;">hash</a> <a href="/tags/linux/" style="font-size: 20px;">linux</a> <a href="/tags/pointer-array/" style="font-size: 10px;">pointer, array</a> <a href="/tags/pseudocode/" style="font-size: 10px;">pseudocode</a> <a href="/tags/rb-tree/" style="font-size: 10px;">rb tree</a> <a href="/tags/sort/" style="font-size: 20px;">sort</a> <a href="/tags/ssh-key/" style="font-size: 10px;">ssh key</a> <a href="/tags/symbol/" style="font-size: 10px;">symbol</a> <a href="/tags/tools/" style="font-size: 10px;">tools</a> <a href="/tags/图/" style="font-size: 10px;">图</a> <a href="/tags/通信协议/" style="font-size: 10px;">通信协议</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/10/26/linux-platform-bus-总线分析/platform/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/10/19/linux-platform-bus-总线分析/">linux platform bus 总线分析</a>
          </li>
        
          <li>
            <a href="/2019/10/17/Linux-Kernel-启动分析/">Linux Kernel 启动分析</a>
          </li>
        
          <li>
            <a href="/2019/09/29/IPv6-NDP/">IPv6 NDP</a>
          </li>
        
          <li>
            <a href="/2019/09/11/十二章-二叉搜索树/">算法导论-第十二章 二叉查找树</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 zhangjun<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>